package srm512;

public class MysteriousRestaurant {
    
    public int maxDays(String[] prices, int budget) {
        int N = prices.length, M = prices[0].length();
        int l, r, m;
        l = 0;
        r = N + 1;

        int[][] cost = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                cost[i][j] = getPrice(prices[i].charAt(j));
            }
        }
        while (r - l > 1) {
            m = (l + r) / 2;
            int tCost = 0;
            for (int i = 0; i < 7; i++) {
                int best = Integer.MAX_VALUE;
                for (int j = 0; j < M; j++) {
                    int c = 0;
                    for (int k = i; k < m; k += 7) {
                        c += cost[k][j];
                    }
                    if (c < best)
                        best = c;
                }
                tCost += best;
            }
            if (tCost <= budget) {
                l = m;
            } else {
                r = m;
            }
        }
        return l;
    }

    private int getPrice(char c) {
        if (c >= '0' && c <= '9')
            return c - '0';
        else if (c >= 'A' && c <= 'Z')
            return c - 'A' + 10;
        else
            return c - 'a' + 36;
    }

    // BEGIN KAWIGIEDIT TESTING
    // Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
    private static boolean KawigiEdit_RunTest(int testNum, String[] p0, int p1, boolean hasAnswer, int p2) {
        System.out.print("Test " + testNum + ": [" + "{");
        for (int i = 0; p0.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print("\"" + p0[i] + "\"");
        }
        System.out.print("}" + "," + p1);
        System.out.println("]");
        MysteriousRestaurant obj;
        int answer;
        obj = new MysteriousRestaurant();
        long startTime = System.currentTimeMillis();
        answer = obj.maxDays(p0, p1);
        long endTime = System.currentTimeMillis();
        boolean res;
        res = true;
        System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
        if (hasAnswer) {
            System.out.println("Desired answer:");
            System.out.println("\t" + p2);
        }
        System.out.println("Your answer:");
        System.out.println("\t" + answer);
        if (hasAnswer) {
            res = answer == p2;
        }
        if (!res) {
            System.out.println("DOESN'T MATCH!!!!");
        } else if ((endTime - startTime) / 1000.0 >= 2) {
            System.out.println("FAIL the timeout");
            res = false;
        } else if (hasAnswer) {
            System.out.println("Match :-)");
        } else {
            System.out.println("OK, but is it right?");
        }
        System.out.println("");
        return res;
    }

    public static void main(String[] args) {
        boolean all_right;
        all_right = true;

        String[] p0;
        int p1;
        int p2;

        // ----- test 0 -----
        p0 = new String[]{"26", "14", "72", "39", "32", "85", "06"};
        p1 = 13;
        p2 = 5;
        all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 1 -----
        p0 = new String[]{"26", "14", "72", "39", "32", "85", "06", "91"};
        p1 = 20;
        p2 = 8;
        all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 2 -----
        p0 = new String[]{"SRM", "512"};
        p1 = 4;
        p2 = 0;
        all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
        // ------------------

        // ----- test 3 -----
        p0 = new String[]{"Dear", "Code", "rsHa", "veFu", "nInT", "heCh", "alle", "ngeP", "hase", "andb", "ecar", "eful"};
        p1 = 256;
        p2 = 10;
        all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
        // ------------------

        if (all_right) {
            System.out.println("You're a stud (at least on the example cases)!");
        } else {
            System.out.println("Some of the test cases had errors.");
        }
    }
    // END KAWIGIEDIT TESTING
}
//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!
